//
// Created by xili on 2024/8/21 20:10.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution1 {
public:
    int findTheWinner(int n, int k) {
        vector<int> ans(n);
        int cnts = n;
        int i = 0;
        for (; i <= n; i++) {
            ans[i] = 1;
        }
        i = 0;
        int step = 0;
        while (cnts != 1) {
            if (ans[i] != 0) {
                step++;
                if (step % k == 0) {
                    ans[i] = 0;
                    cnts--;
                }
            }
            i = (i + 1) % n;
        }
        for (i = 0; i < n; i++) {
            if (ans[i]) {
                return i + 1;
            }
        }
    }
};

//队列
class Solution2 {
public:
    int findTheWinner(int n, int k) {
        queue<int> qu;
        for (int i = 1; i <= n; i++) {
            qu.emplace(i);
        }
        while (qu.size() > 1) {
            for (int i = 1; i < k; i++) {
                qu.emplace(qu.front());
                qu.pop();
            }
            qu.pop();
        }
        return qu.front();
    }
};